#include "parser.h"
#include "pn.h"
#include "util.h"

extern pn sw;
extern double THRESH;
extern int BEAM;
extern int WINDOW;
extern vector <string> n2s;

int parser::getInd(pn &tsw, const vector <int> &si, const vector <int> &postagi, int i, int j, const vector <int> &ntw, const vector <int> &ntp, bool ef) const { 
   vector <int> w,p,bw,aw,bp,ap;
   for (int e=i; e<=j; ++e) {
      w.push_back(si[e]);
      p.push_back(postagi[e]);
   }
   int ii=i-WINDOW;
   if (ii < 0) ii=0;
   for (int e=ii; e<i; ++e) {
      bw.push_back(si[e]);
      bp.push_back(postagi[e]);
   }
   int jj=j+WINDOW;
   if (jj > si.size()-1) jj=si.size()-1;
   for (int e=j+1; e<=jj; ++e) {
      aw.push_back(si[e]);
      ap.push_back(postagi[e]);
   }
   posNeg ae(w,p,bw,aw,bp,ap,ntw,ntp,ef); 
   return tsw.add(ae);
}

bool parser::firstAssign(vector <int> &start, vector <int> &end, int i, int j) const {
   assert(start.size()==end.size());
   assert(start.size() > 0);
   if (j-i+1 < start.size()) return false;

   start[0] = i;
   for (int a=1; a<start.size(); ++a) {
      start[a] = a+i;
   }
   end[end.size()-1] = j;
   for (int a=(int)end.size()-2; a>=0; --a) {
      if (start[a+1] < end[a+1]) {
	 end[a] = start[a+1];
      }
      else end[a] = start[a];
   }
   return true;
}

bool parser::nextAssign(vector <int> &start, vector <int> &end, int i, int j) const {
   for (int a=(int)start.size()-1; a>0; --a) {
      if (start[a] < end[a]-1) {
	 ++start[a];
	 for (int b=a+1; b<start.size(); ++b) {
	    start[b] = start[b-1]+1;
	    end[b-1] = start[b];
	 }
	 end[a-1] = start[a]; 
	 return true;
      }
   }
   return false;
}

bool parser::nextInd(vector <int> &v, const vector <int> &m) const {
   for (int i=(int)v.size()-1; i>=0; --i) {
      if (v[i] < m[i]) {
         ++v[i];
         return true;
      }
      else v[i] = 0;
   }
   return false;
}

sie parser::recover(const  vector <vector <vector <vector <state> > > > &p, const vector <leaf> &le, const vector <int> &intt, int n, int s, int e, int ind) const {
   sie r(n2s[intt[n]]);
   r.putSEW(le[s].giveS(),le[e].giveE());
   r.putProb(p[n][s][e][ind].prob);

   for (int i=0; i<p[n][s][e][ind].c.size(); ++i) {
      inde in = p[n][s][e][ind].c[i];
      //cout<<ntt[in.nt]<<" "<<in.s<<" "<<in.e<<" "<<in.ind<<"\n";
      //cout<<p[in.nt][in.s][in.e].size()<<"\n";
      sie c = recover(p,le,intt,in.nt,in.s,in.e,in.ind);
      r.addChild(c);
   }
   return r;
}


void parser::parse(const vector <leaf> &le, const vector <classifier> &cl, const vector <int> &words, const vector <int> &postags, const vector <cover> &co, const vector <int> &iterms, const vector <int> &inonterms, int istart, vector <sie> &r) const {

   pn tsw; // to store examples encountered in this parsing

   vector <int> intt; // a list of both terminals and non-terminals
   for (int i=0; i<iterms.size(); ++i) intt.push_back(iterms[i]);
   for (int i=0; i<inonterms.size(); ++i) intt.push_back(inonterms[i]);

   vector <vector <vector <vector <state> > > > p(intt.size()); // data structure for the CYK algorithm
   for (int i=0; i<p.size(); ++i) {
      p[i].resize(le.size());
      for (int j=0; j<p[i].size(); ++j) {
         p[i][j].resize(le.size());
      }
   }

   // put penultimate-leaf probabilities
   for (int i=0; i<le.size(); ++i) {
      int covered=-1;
      for (int j=0; j<co.size(); ++j) {
	 if (co[j].giveS()==i && co[j].giveE()==i) {
	    covered=j;
	    break;
	 }
      }
      for (int c=0; c<cl.size(); ++c) {
	 vector <int> rhs = cl[c].giveiRhs();
	 if (rhs.size()==1 && rhs[0]==le[i].giveNt()) {
	    int ntr = findWhere(intt,cl[c].giveiLhs());
	    if (covered != -1) { // if told that covered by the same non-terminal then prob=1 but if covered by a different non-terminal then prob=0 
	       state s;
	       if (cl[c].giveiLhs()==co[covered].giveNt()) {
		  s.prob=1;
	       }
	       else {
		  s.prob=0;
	       }
	       p[ntr][i][i].push_back(s);
	    }
	    else { // calculate probability
	       vector <int> ntw,ntp;
	       ntw.push_back(rhs[0]);
	       ntp.push_back(rhs[0]);
	       int index = getInd(tsw,words,postags,le[i].giveS(),le[i].giveE(),ntw,ntp,cl[c].isTerm());
	       double prob = cl[c].giveP(index,tsw);
	       state s;
	       s.prob=prob;
	       p[ntr][i][i].push_back(s);
	    }
	 }
      }
   }

   // storing rhs information that will be used many times
   vector <vector <int> > clrhs, clri;
   for (int c=0; c<cl.size(); ++c) { 
      vector <int> rhs = cl[c].giveiRhs();
      clrhs.push_back(rhs);
      vector <int> ri(rhs.size());
      for (int r=0; r<rhs.size(); ++r) ri[r] = findWhere(intt,rhs[r]);
      clri.push_back(ri);
   }
   // start of CYK
   for (int e=0; e<le.size(); ++e) { // for every substring length
      for (int i=0; i+e<le.size(); ++i) { // for every start position
         int j = i + e;
	 vector <bool> considered(p.size(),false);
	 bool atLeastOneConsidered=true;
	 while (atLeastOneConsidered) { // to take into account interdependencies between non-terminals which may cover the same length in different order
	    atLeastOneConsidered=false;
	    for (int n=0; n<p.size(); ++n) { // for every terminal/non-terminal
	       if (considered[n]) continue;
	       for (int c=0; c<cl.size(); ++c) { // test every production
		  if (cl[c].giveiLhs() != intt[n]) continue;
		  if (clrhs[c].size() > e+1) continue;
		  if (clrhs[c].size() > 2 && clrhs[c].size() != e+1) continue;
		  if (cl[c].giveiLhs()==istart) {
		     if (i != 0 || j != le.size()-1) continue;
		  }
		  // different start & end positions for the rhs nonterms/terms
		  vector <int> start(clri[c].size());
		  vector <int> end(clri[c].size());
		  bool f=firstAssign(start,end,i,j);
		  while (f) {
		     // check if at least one rhs combination is present
		     bool g=true;
		     for (int r=0; r<clri[c].size(); ++r) {
			if (p[clri[c][r]][start[r]][end[r]].size()==0) {
			   g=false;
			   break;
			}
		     }
		     if (g) {
			vector <int> ntw,ntp;
			ntw.push_back(clrhs[c][0]);
			ntp.push_back(clrhs[c][0]);
			for (int r=1; r<clri[c].size(); ++r) {
			   for (int a=le[r-1].giveE()+1; a<le[r].giveS(); ++a) {
			      ntw.push_back(words[a]);
			      ntp.push_back(postags[a]);
			   }
			   ntw.push_back(clrhs[c][r]);
			   ntp.push_back(clrhs[c][r]);
			}
			int index = getInd(tsw,words,postags,le[i].giveS(),le[j].giveE(),ntw,ntp,cl[c].isTerm());
			// calling the classifier
			double prob = cl[c].giveP(index,tsw);
			//writeVector(cout,cl[c].giveProd());
			//tsw.writeStr(cout,index);
			//cout<<"PROB: "<<prob<<"\n\n";
			if (prob > THRESH) {
			   vector <int> ind(clri[c].size(),0);
			   vector <int> ma(clri[c].size());
			   for (int r=0; r<clri[c].size(); ++r) {
			      ma[r] = p[clri[c][r]][start[r]][end[r]].size()-1;
			   }
			   bool h=true;
			   while (h) {
			      double conf=prob;
			      vector <inde> in;
			      for (int r=0; r<clri[c].size(); ++r) {
				 // combining confidences
				 conf *= p[clri[c][r]][start[r]][end[r]][ind[r]].prob;
				 in.push_back(inde(clri[c][r],start[r],end[r],ind[r]));
			      }
			      if (conf > THRESH) {
				 state s;
				 s.prob=conf;
				 s.iprod = cl[c].giveIprod();
				 s.c=in;
				 if (find(p[n][i][j].begin(), p[n][i][j].end(), s)==p[n][i][j].end()) {
				    p[n][i][j].push_back(s);
				    atLeastOneConsidered = true;
				    considered[n]=true;
				 }
			      }
			      h=nextInd(ind,ma);
			   }
			}
		     }
		     f=nextAssign(start,end,i,j);
		  }
	       }
	       sort(p[n][i][j].begin(), p[n][i][j].end());
	       if (p[n][i][j].size() > BEAM) p[n][i][j].resize(BEAM);
	    }
	 }
      }
   }

   /*for (int n=0; n<p.size(); ++n) {
      for (int i=0; i<p[n].size(); ++i) {
	 for (int j=0; j<p[n][i].size(); ++j) {
	    for (int k=0; k<p[n][i][j].size(); ++k) {
	       cout<<n2s[intt[n]]<<" "<<i<<" "<<j<<" "<<p[n][i][j][k].prob<<"\n";
	    }
	 }
      }
   }*/

   // recover parses
   for (int n=0; n<p.size(); ++n) {
      if (intt[n]==istart) {
         if (p[n][0][le.size()-1].size() != 0) {
            //cout<<"YES\n";
            for (int i=0; i<p[n][0][le.size()-1].size(); ++i) {
               sie re = recover(p,le,intt,n,0,le.size()-1,i);
               r.push_back(re);
               //cout<<re<<"\n\n";
            }
         }
      }
   }
 //  cout<<"----------------------------------------\n";
}
